
/*
 * Copyright (C) 2008-2009 Archie L. Cobbs. All rights reserved.
 *
 * $Id: GarbageCollector.java 377 2010-03-11 20:50:18Z archie.cobbs $
 */

package org.dellroad.sidekar.gc;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.dellroad.sidekar.Database;
import org.dellroad.sidekar.Entity;
import org.dellroad.sidekar.Item;
import org.dellroad.sidekar.query.QueryIterable;
import org.dellroad.sidekar.query.QueryIterator;

/**
 * Detaches unreferenced and unwanted items from a database using mark/sweep garbage collection.
 *
 * <p>
 * Instances are configured with a set of {@link Entity}s whose (exact) instances are <i>candidates</i> for garbage collection.
 * Then during a collection operation, a <i>root set</i> is provided (or computed) and all candidates that are
 * not reachable from the root set are detached.
 * </p>
 *
 * <p>
 * This class optimizes the mark and sweep phases based on static analysis of the database schema, in that
 * we only follow references that can possibly lead to a garbage candidate, and we eliminate from the root
 * set entities that cannot reference garbage candidates (when possible).
 * </p>
 *
 * <p>
 * Callers must provide a {@link Marker} which keeps tracks of which {@link Item}s have been seen during a run.
 * </p>
 */
public class GarbageCollector {

    private final Database db;
    private final Marker marker;

    /**
     * Constructor.
     *
     * @param db database to collect garbage from
     * @param marker used to track objects visited
     * @throws IllegalArgumentException if {@code db} is null
     */
    public GarbageCollector(Database db, Marker marker) {
        if (db == null)
            throw new IllegalArgumentException("null db");
        this.db = db;
        this.marker = marker;
    }

    /**
     * Detach unreferenced and unwanted items from the configured database using mark/sweep garbage collection.
     * All {@link Item}s that are instances of an {@link Entity} in {@code candidates} (or any sub-{@link Entity}
     * thereof) and that are not reachable from any {@link Item} in the root set will be detached.
     *
     * <p>
     * In this method, the root set is the set of all {@link Item}s that are <i>not</i> instances
     * of an {@link Entity} in {@code candidates} (or any sub-{@link Entity} thereof).
     * </p>
     *
     * @param candidates entities whose instances (and sub-entity instances) are to be considered
     *  candidates for garbage collection
     * @throws IllegalArgumentException if {@code candidates} contains any invalid entries
     * @return the number of {@link Item}s detached from the database
     * @see #collect(Set, Set)
     * @see #collect(Set, Iterator)
     */
    public long collect(Set<Entity<?>> candidates) {
        if (candidates == null)
            throw new IllegalArgumentException("null candidates");
        return this.collect(candidates, new RootSetBuilder() {
            public List<QueryIterable<?>> buildRootSet(GarbageCollection gc) {
                ArrayList<QueryIterable<?>> list = new ArrayList<QueryIterable<?>>();
                for (Entity<?> entity : GarbageCollector.this.db.getEntities()) {

                    // Don't include garbage in the root set
                    if (gc.isCandidate(entity))
                        continue;

                    // Don't include anything that can't reference garbage in the root set
                    if (!gc.canReferenceCandidates(entity))
                        continue;

                    // Skip abstract entities
                    if (entity.isAbstract())
                        continue;

                    // Add all of this entity's items to the root set
                    list.add(entity.query(true));
                }
                return list;
            }
        });
    }

    /**
     * Detach unreferenced and unwanted items from the configured database using mark/sweep garbage collection.
     * All {@link Item}s that are instances of an {@link Entity} in {@code candidates} (or any sub-{@link Entity}
     * thereof) and that are not reachable from any {@link Item} in the root set will be detached.
     *
     * <p>
     * In this version of the method, the root set is the set of all {@link Item}s that are instances
     * of any {@link Entity} in {@code rootEntities} (or any sub-{@link Entity} thereof).
     * If an entity (or sub-entity) is in both {@code candidates} and  {@code rootEntities},
     * it's presence in {@code candidates} will be ignored.
     * </p>
     *
     * @param candidates entities whose instances (and sub-entity instances) are to be considered
     *  candidates for garbage collection
     * @param rootEntities entities whose instances (and sub-entity instances) constitute the root set
     * @throws IllegalArgumentException if {@code candidates} or {@code rootEntities} contains any invalid entries
     * @return the number of {@link Item}s detached from the database
     * @see #collect(Set)
     * @see #collect(Set, Iterator)
     */
    public long collect(Set<Entity<?>> candidates, Set<Entity<?>> rootEntities) {

        // Check roots
        if (!this.db.getEntities().containsAll(rootEntities))
            throw new IllegalArgumentException("one or more root entities is invalid");

        // Add all descendant entities to root set
        rootEntities = new HashSet<Entity<?>>(rootEntities);
        this.transitivelyCloseUnderDescendant(rootEntities);

        // Remove from the set of candidates any entities that are also in the root set
        candidates = new HashSet<Entity<?>>(candidates);
        candidates.removeAll(rootEntities);

        // Build root set by concatenating root set entities' iterators
        final Set<Entity<?>> rootSet = rootEntities;
        return collect(candidates, new RootSetBuilder() {
            @Override
            public List<QueryIterable<?>> buildRootSet(GarbageCollection gc) {
                ArrayList<QueryIterable<?>> list = new ArrayList<QueryIterable<?>>();
                for (Entity<?> entity : rootSet) {
                    if (!entity.isAbstract())
                        list.add(entity.query(true));
                }
                return list;
            }
        });
    }

    /**
     * Detach unreferenced and unwanted items from the configured database using mark/sweep garbage collection.
     * All {@link Item}s that are instances of an {@link Entity} in {@code candidates} (or any sub-{@link Entity}
     * thereof) and that are not reachable from any {@link Item} in the root set will be detached.
     *
     * <p>
     * In this version of the method, the caller provides the root set explicitly via {@code roots}.
     * </p>
     *
     * @param candidates entities whose instances (and sub-entity instances) are to be considered
     *  candidates for garbage collection
     * @param roots iterates over the root set
     * @throws IllegalArgumentException if {@code candidates} or {@code rootEntities} contains any invalid entries
     * @return the number of {@link Item}s detached from the database
     * @see #collect(Set)
     * @see #collect(Set, Set)
     */
    public long collect(Set<Entity<?>> candidates, final Iterator<?> roots) {
        @SuppressWarnings("unchecked")
        final QueryIterator<Object> queryIterator = roots instanceof QueryIterator ?
          (QueryIterator<Object>)roots : new QueryIterator<Object>() {
            @Override
            public boolean hasNext() {
                return roots.hasNext();
            }
            @Override
            public Object next() {
                return roots.next();
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
            @Override
            public void close() {
            }
            @Override
            public boolean isReadOnly() {
                return true;
            }
        };
        final QueryIterable<?> queryIterable = new QueryIterable<Object>() {
            @Override
            public QueryIterator<Object> iterator() {
                return queryIterator;
            }
            @Override
            public boolean isReadOnly() {
                return true;
            }
        };
        return collect(candidates, new RootSetBuilder() {
            public List<QueryIterable<?>> buildRootSet(GarbageCollection gc) {
                return Collections.<QueryIterable<?>>singletonList(queryIterable);
            }
        });
    }

    /**
     * Do the GC and ensure we close things up properly
     *
     * @throws IllegalArgumentException if {@code candidates} contains any invalid entries
     */
    private long collect(Set<Entity<?>> candidates, RootSetBuilder rootSetBuilder) {

        // Prep candidate entities
        if (candidates == null)
            candidates = this.db.getEntities();
        if (!this.db.getEntities().containsAll(candidates))
            throw new IllegalArgumentException("one or more candidate entities is invalid");
        candidates = new HashSet<Entity<?>>(candidates);
        this.transitivelyCloseUnderDescendant(candidates);

        // Create GC object
        GarbageCollection gc = new GarbageCollection(this.db, this.marker, candidates);

        // Reset marker
        this.marker.reset();
        try {

            // Do mark
            gc.mark(rootSetBuilder.buildRootSet(gc));

            // Do sweep
            return gc.sweep();
        } finally {

            // Close marker
            this.marker.close();
        }
    }

    // Add all descendents to a set
    private void transitivelyCloseUnderDescendant(Set<Entity<?>> entities) {
        for (Entity<?> entity : this.db.getEntities()) {
            if (containsAncestorOf(entities, entity))
                entities.add(entity);
        }
    }

    // Determine if the given set contains a (strict) ancestor of the given entity
    private static boolean containsAncestorOf(Set<Entity<?>> set, Entity<?> entity) {
        for (Entity<?> ancestor = entity.getParent(); ancestor != null; ancestor = ancestor.getParent()) {
            if (set.contains(ancestor))
                return true;
        }
        return false;
    }

    // Interface for building root sets
    private static interface RootSetBuilder {
        List<QueryIterable<?>> buildRootSet(GarbageCollection gc);
    }
}

